/*****************************************************************************
 * 
 * Copyright [2013] [Mervin.Wong]
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *       http://www.apache.org/licenses/LICENSE-2.0
 *       
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *  
 *****************************************************************************/
package util;

import base.Global.NumberType;

/**
 * FibonacciHeap
 * @package util
 * @author mervin
 ****************************************************************************
 * 属性
 * nodeNum //节点数量
 * rootNode //根节点
 * maxDegree //最大的度
 * 基本操作：
 * 	=1, creat//创建
 * 	2, insert//插入一个节点
 *  3, minNode//寻找最小节点
 *  4, union //合并
 *  5，extractMin//抽取最小节点
 *  6, decreaseKey//减小一个关键字
 *  7，delete//删除一个节点
 *
 *
 *
 ****************************************************************************
 */
public class FibonacciHeap {
	
	public int nodeNum = 0;
	public int maxDegree = 0;
	public Node rootNode = null;
	
	/**
	 * 构造函数
	 */
	public FibonacciHeap(){
	}
/*	private void creat(){
	}*/
	
	/**
	 * @name insert
	 * @description 插入一个节点
	 * @param key
	 */
	public void insert(Number id, int key){
		if(this.rootNode == null){
			//堆是空的
			this.rootNode = new Node(id, key, 0, null, null);
			this.rootNode.setLeft(this.rootNode);
			this.rootNode.setRight(this.rootNode);
		}else{
			//1,插入到根列表
			Node node = new Node(id, key, 0, null, null);
			node.setLeft(this.rootNode);//插入到rootNode的右边
			node.setRight(this.rootNode.getRight());
			
			this.rootNode.getRight().setLeft(node);//*
			this.rootNode.setRight(node);
			//2 更新最小节点
			if(this.rootNode.getkey() > key){
				this.rootNode = node;
			}
		}
		
		this.nodeNum++;
	}
	
	/**
	 * @name minNode
	 * @description 获取最小节点
	 * @return
	 */
	public Node minNode(){
		return this.rootNode;
	}
	
	/**
	 * @name union
	 * @description 合并两个堆
	 * @param heap
	 * @return
	 */
	public FibonacciHeap union(FibonacciHeap heap){
		Node h2 = heap.rootNode;
		Node h3 = null;
		FibonacciHeap heap3 = new FibonacciHeap();
		h3 = heap3.rootNode = this.rootNode;
		Node right = h3.getRight();
		Node left = h2.getLeft();
		
		h3.setRight(h2);
		h2.setLeft(h3);
		
		right.setLeft(left);
		left.setRight(right);
		
		if(h3.getkey() > h2.getkey()){
			heap3.rootNode = heap.rootNode;
		}
		heap3.nodeNum = this.nodeNum+heap.nodeNum;
		return heap3;
	}
	
	/**
	 * @name extractMin
	 * @description 提取最小的节点
	 * @return
	 */
	public Node extractMin(){
		Node node = null;
		node = this.rootNode;
		if(node != null){
			Node child = null;
			Node next = null;
			if((child = node.getChild()) != null ){
				//将子节点的父节点设为NULL
				do{
					child.setParent(null);
				}while((next = child.getRight()) != null && next.getId().equals(child.getId()));
				
				
				Node childRight = child.getRight();
				Node nodeLeft = node.getLeft();
				Node nodeRight = node.getRight();
				
				child.setRight(nodeRight);
				nodeRight.setLeft(child);
				childRight.setLeft(nodeLeft);
				nodeLeft.setRight(childRight);
				
			}
			if(node.getRight().equals(node)){
				this.rootNode = null;
			}else{
				this.rootNode = node.getRight();
			}
			this.nodeNum--;
		}
		return node;
	}
	
	/**
	 * @name link
	 * @description 将node1从原始的节点链中去掉，然后加入到node2的子节点中
	 * @param node1
	 * @param node2
	 */
	public void link(Node node1, Node node2){
		//1 将node1从原始的节点链中去掉
		Node right = node1.getRight();
		if(right.getParent() != null){
			right.getParent().setChild(right);
		}
		right.setLeft(node1.getLeft());
		node1.getLeft().setRight(right);
		
		//2 加入到node2的子节点中
		Node left = node2.getLeft();
		
		node1.setLeft(left);
		node1.setRight(node2);
		
		left.setRight(node1);
		node2.setLeft(left);
		
		//3 node2的degree＋＋
		node2.setDegree(node2.getDegree()+1);
	}
	
}
/**
 * 斐波那契堆的节点
 * @author mervin
 *****************************************************************************
 * 属性：
 *	 key // 值
 *	degree //度
 *  parent //父节点
 *  child //子节点
 *  left //左兄弟
 *  right //右兄弟
 *  marked //该节点从上一次成为另一个节点的子女以后，它是否失掉一个孩子
 *  
 *   
 *****************************************************************************
 */
class Node{
	private Number id = null;
	private int key;
	private int degree = 0;
	private Node parent = null;
	private Node child = null;
	private Node left = null;
	private Node right = null;
	private boolean marked = false;

	Node(Number id, int key, int degree, Node parent, Node child){
		this.id = MathTool.str2Num(NumberType.LONG, id.toString());;
		this.key = key;
		this.degree = degree;
		this.parent = parent;
		this.child = child;
	}
	
	Node(Number id, int key, int degree, Node parent, Node child, Node left, Node right, boolean marked){
		this.id = MathTool.str2Num(NumberType.LONG, id.toString());;
		this.key = key;
		this.degree = degree;
		this.parent = parent;
		this.child = child;
		this.left = left;
		this.right = right;
		this.marked = marked;
	}
	
	/**
	 * set param
	 * @param key
	 */
	public void setId(Number id){
		this.id = MathTool.str2Num(NumberType.LONG, id.toString());
	}
	public void setKey(int key){
		this.key = key;
	}
	public void setDegree(int degree){
		this.degree = degree;
	}
	public void setParent(Node parent){
		this.parent = parent;
	}
	public void setChild(Node child){
		this.child = child;
	}
	public void setLeft(Node left){
		this.left = left;
	}
	public void setRight(Node right){
		this.right = right;
	}
	public void setMarked(boolean marked){
		this.marked = marked;
	}
	
	/**
	 * get param
	 * @return
	 */
	public Number getId(){
		return this.id;
	}
	public int getkey(){
		return this.key;
	}
	public int getDegree(){
		return this.degree;
	}
	public Node getParent(){
		return this.parent;
	}
	public Node getChild(){
		return this.child;
	}
	public Node getLeft(){
		return this.left;
	}
	public Node getRight(){
		return this.right;
	}
	public boolean getMarked(){
		return this.marked;
	}
}
